package LeetCode.interview;

import LeetCode.interview._021_Merge_Two_Sorted_Lists.ListNode;
import LeetCode.interview._101_Symmetric_Tree.TreeNode;
import util.LogUtils;

/*
 * 
原题

　　Given a binary tree, find its maximum depth. 
　　The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. 

题目大意

　　给定一棵两叉树，求它的最大深度。 
	注：最大深度其实就是求整棵树的深度（从根节点开始到最底层）
 * @Date 2017-09-13 21：17
 */
public class _104_Maximum_Depth_of_Binary_Tree {
	
	public class TreeNode {
	    int val;
	    TreeNode left;
	    TreeNode right;
	    TreeNode(int x) { val = x; }
	    public TreeNode(int x, TreeNode l, TreeNode r) {val = x; left = l; right = r;}
	}
	
	
	/**
	 * 法一：My
	 * @param root
	 * @return
	 */
    public int maxDepth(TreeNode root) {
    	if (root == null)	return 0;
        return traverseCal(root)+1;	
    }
    
    private int traverseCal(TreeNode root) {
    	if (root == null)	return 1;		//叶子节点为1
    	int ld = 0, rd = 0;
    	if (root.left != null)
    		ld = traverseCal(root.left)+1;
    	if (root.right != null)
    		rd = traverseCal(root.right)+1;
    	return Math.max(ld, rd);
    }
    
    
    /*
     * 法二：其实没差。。。
     */
    public int maxDepth2(TreeNode root) {
        if (root == null) {
            return 0;
        } else if (root.left == null && root.right == null) {
            return 1;
        } else {
            int left = maxDepth(root.left);
            int right = maxDepth(root.right);
            return 1 + (left > right ? left : right);
        }
    }
    
    
	private TreeNode newTree1() {
		return new TreeNode(1, 
					new TreeNode(2, 
							new TreeNode(3, null, 
									new TreeNode(4)
							), null 
					), 
					new TreeNode(2, 
							null, 	new TreeNode(3, new TreeNode(4), null)
					)
				);
	}
	
	private TreeNode newTree2() {
		return new TreeNode(1, 
					new TreeNode(2, 
							new TreeNode(4, 
									new TreeNode(6), new TreeNode(7,
															null, new TreeNode(8))
							), new TreeNode(5)
					), 
					new TreeNode(3, 
							null, 	null)
				);
	}
	
	
	public static void main(String[] args) {
		_104_Maximum_Depth_of_Binary_Tree obj = new _104_Maximum_Depth_of_Binary_Tree();
		LogUtils.println("结果", 
				obj.maxDepth(
						obj.newTree2()
				));
	}
}
